package 算法;


import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个字符串和一个单词词典，问这个字符串是否能被划分成字典中的单词。比如如果词典是{"apple", "orange", "pie"},
 * “applepie”可以划分为apple/pie；applepieapple 可以划分为 "apple/pie/apple", 但是“appie”就无法划分
*
* *
* */
public class 单词词典 {


    public static void main(String[] args) {

        Set<String> dics = new HashSet<>();
        dics.add("apple");
        dics.add("orange");
        dics.add("pie");



        System.out.println(execute("applepiedsds", dics));

        System.out.println();

        System.out.println(execute("appleorange", dics));



    }

    /**
     * @param tag  目标字符串
     * @param dics 字典
     * @return
     */
    private static String execute(String tag, Set<String> dics) {

        StringBuilder outBuilder = new StringBuilder();

        ergodicArray(tag.toCharArray(), 0, dics, outBuilder);

        return outBuilder.toString();
    }


    /**
     * 遍历数组
     *
     * @param chars      目标字符串的数组
     * @param start      数组下标
     * @param dict       字典
     * @param outBuilder 输出对象
     */
    public static void ergodicArray(char[] chars, int start, Set<String> dict, StringBuilder outBuilder) {
        //数组遍历完成退出
        if (start == chars.length) {
            return;
        }

        // 下一个单词的对象
        StringBuilder headWord = new StringBuilder();

        //是否完成一个单词的查询
        boolean isBreak = true;
        //从下标位开始遍历
        for (int i = start; i < chars.length; i++) {

            headWord.append(chars[i]);
            //比较字典内数据是否有匹配，如果是进入二次递归遍历
            if (dict.contains(headWord.toString())) {

                outBuilder.append(headWord).append("/");
                ergodicArray(chars, ++i, dict, outBuilder);
                isBreak = false;
                break;
            }
        }
        if (isBreak) {
            outBuilder.append("\n末尾不合法字符").append(headWord.toString());
        }

    }

}
